﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using ZuoAlgorithms.Class030;


// 随机快速排序
// 测试链接 : https://www.luogu.com.cn/problem/P1177
namespace ZuoAlgorithms.Class023;
public class Code01_QuickSort
{
    public static int MAXN = 100001;

    public static int[] arr = new int[MAXN];

    public static int n;

    // 随机快速排序经典版
    public static void QuickSort1(int l, int r)
    {
        if (l >= r)
            return;
        Random random = new Random();
        int x = arr[l + (int)(random.Next() * (r - l + 1))];
        int mid = Partition1(l, r, x);
        QuickSort1(l, mid - 1);
        QuickSort1(mid + 1, r);
    }

    public static int Partition1(int l, int r, int x)
    {
        int a = l;
        int xi = 0;
        for (int i = l; i <= r; i++)
        {
            if (arr[i] <= x)
            {
                Swap(a, i);
                if (arr[a] == x)
                {
                    xi = a;
                }
                a++;
            }
        }
        Swap(xi, a - 1);
        return a - 1;
    }

    public static void Swap(int i, int j)
    {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 随机快速排序改进版
    public static void QuickSort2(int l, int r)
    {
        if (l >= r)
            return;
        Random random = new Random();
        int x = arr[l + (int)(random.Next() * (r - l + 1))];
        Partition2(l, r, x);
        int left = first;
        int right = last;
        QuickSort2(l, left - 1);
        QuickSort2(right + 1, r);
    }

    // 荷兰国旗问题
    public static int first, last;

    // 已知arr[l....r]范围上一定有x这个值
    // 划分数组 <x放左边，==x放中间，>x放右边
    // 把全局变量first, last，更新成==x区域的左右边界
    public static void Partition2(int l, int r, int x)
    {
        first = l;
        last = r;
        int i = l;
        while (i <= last)
        {
            if (arr[i] == x)
            {
                i++;
            }
            else if (arr[i] < x)
            {
                Swap(first++, i++);
            }
            else
            {
                Swap(i, last--);
            }
        }

    }
}
